// Package 递归反转单链表 main
// @Title 递归反转单链表
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-18 19:38
// @Create  2022-01-18 19:38
package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

//
//  reverseRecursion
//  @Description: 使用递归的方式来翻转一个单链表
//  @param curNode：
//  @return *ListNode：
//
func reverseRecursion(curNode *ListNode) *ListNode {
	if curNode == nil || curNode.Next == nil {
		return curNode
	}

	newNode := reverseRecursion(curNode.Next)
	curNode.Next.Next = curNode
	curNode.Next = nil
	return newNode
}

//
//  reverseLinkListTwoPoint
//  @Description: 使用双指针的方式翻转一个单链表
//  @param head：单链表头指针
//  @return *ListNode：翻转后的单链表头指针
//
func reverseLinkListTwoPoint(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	var pre *ListNode
	cur := head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

//
//  reverseLinkListStack
//  @Description: 使用栈的方式实现翻转单链表
//  @param head：
//  @return *ListNode：
//
func reverseLinkListStack(head *ListNode) *ListNode {
	if head == nil {
		return nil
	}
	var pre *ListNode
	stack := []*ListNode{}
	cur := head
	for cur != nil {
		stack = append(stack, cur)
		cur = cur.Next
	}
	for len(stack) > 0 {
		// 出栈
		tempNode := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		tempNode.Next = pre
		pre = tempNode
	}
	return pre
}

//
//  display
//  @Description: 打印链表的节点
//  @param head： 链表的头结点
//  @return []int：链表数组
//
func display(head *ListNode) []int {
	if head == nil {
		return nil
	}
	var ans []int
	for head != nil {
		ans = append(ans, head.Val)
		head = head.Next
	}
	return ans
}

func main() {
	root := ListNode{
		0,
		&ListNode{
			1,
			&ListNode{
				2,
				&ListNode{
					3,
					nil,
				},
			},
		},
	}
	fmt.Println(display(&root))
	res := reverseRecursion(&root)
	fmt.Println(display(res))
}
